#ifndef DICCTRIE_H
#define DICCTRIE_H

#include <iostream>
#include <string>
#include "ConjString.h" 


using namespace std;

template< class T>
struct Nodo{

	Nodo* hijos[27];
	T *significado;
	bool finClave;

};

template <class T>
bool hayMasRamas (const Nodo<T> &n, int i) {
	int i2 = 0;
	bool retorno = false;
	while (i2 < 27 && !retorno) {
		if (i2 != i)
			retorno = (n.hijos[i2] != NULL);
		i2++;
	}
	return retorno;
}

template <class T>
bool esUnaHoja(const Nodo<T> &n) {

	int i = 0;
	bool retorno = true;
	while ( i < 27 && retorno) {
		if (n.hijos[i] != NULL) {
			retorno = false;
		}
		i++;
	}
	return retorno;
}

template <class T>
void borrarRama(Nodo<T> ** &n) {

	
	Nodo<T> *aux;
	aux = *n;
	int i = 0;
	while (i != 27) {

		i = 0;
		while ((*n) -> hijos[i] == NULL && i != 27) {
			i++;
		}
		if (i != 27) {
			*n = (*n) -> hijos[i];
			delete (aux -> significado);
			delete aux;
			aux = *n;
		}

	}
	aux = *n;
	delete (aux -> significado);
	delete aux;
	*n = NULL;
}

template< class T >
class DiccTrie {
	
public:
	DiccTrie();
	~DiccTrie();
	const T &obtener( const string &clave ) const;
	
	void definir( const string &clave, const T &significado );
	bool esClave( const string &clave ) const;
	const ConjString  & claves() const;
	void borrar(const string &clave);
	DiccTrie<T> &operator=(const DiccTrie<T> &otro);
	template<class T2>
	friend ostream & operator<<(ostream &o, const DiccTrie<T2> &esp);

private:
	int indizar(const char &c) const{ return (int) c - 97; }

	
	Nodo< T > *nodo;
	ConjString cClaves;
};

template<class T>
DiccTrie<T>::DiccTrie() {
	nodo = NULL;
	
}	

template<class T>
const ConjString & DiccTrie<T>::claves() const {
	return cClaves;
}

template<class T>
DiccTrie<T>::~DiccTrie() {
	string aux;

	IteradorConjString it(cClaves);

	while ( it.tieneProximo() ) {
		borrar(it.proximo());
	}
}

template<class T>	
void DiccTrie<T>::definir( const string &clave, const T &sig){
	Nodo<T> *p;
	int i = 0;
	int j = 0;

	if (nodo == NULL) {
		nodo = new Nodo<T>();
		while (i < 27) {
			nodo -> hijos[i] = NULL;
			i++;
		}
	}
	p = nodo;
	while ( j < clave.length() ) {
		i = 0;
		if( p -> hijos[char2nat(clave[j])] == NULL ) {
			p -> hijos[char2nat(clave[j])] = new Nodo<T>();
			while ( i < 27) {
				(p -> hijos[char2nat(clave[j])]) -> hijos[i] = NULL;
				i++;
			}			
			p -> hijos[char2nat(clave[j])] -> finClave = false;
		}
		p = p -> hijos[char2nat(clave[j])];
		j++;
	}
 	p -> finClave = true;
	
	if (p -> significado == NULL) {
	(p -> significado) = new T();
	*(p -> significado) = sig;
	}
	else 

	*(p -> significado) = sig;
	cClaves.agregar(clave);
}

template <class T>
bool DiccTrie<T>::esClave( const string &clave ) const{
	Nodo<T> *p;
	bool retorno;
	p = nodo;
	retorno = true;
	int i = 0;
	
	if ( p == NULL ){
		retorno = false; // si el trie es nulo devuelve falso para cualquier elemento
	}else {
		while (i < clave.length() && retorno)  /* va a bajar en el trie hasta agotar el String */{
			if (p -> hijos[char2nat(clave[i])] == NULL ) {
				retorno = false; // si no puede seguir devuelve false
			}else 
				p = p -> hijos[char2nat(clave[i])];
			i++;			
		}		
		if (retorno)
			retorno = p -> finClave;
	}
	return retorno;

}

template <class T>
const T & DiccTrie<T>::obtener( const string &clave ) const{
	// precondición: la clave pertenece al diccionario
	
	if(!this->esClave(clave)){
		cout << "Error: la clave '"<< clave << "' no existe en este diccionario" << endl;
	}

	Nodo<T> *p;
	p = nodo;
	int i = 0;
	while ( i < clave.length()) {
		p = p -> hijos[char2nat(clave[i])];
		i++;
	}
	return *(p -> significado);
}

template <class T>
void DiccTrie<T>::borrar(const string &clave) {

	bool encontrado, aux;
	Nodo<T> *p, **p1;
	int i = 0;
	char proxAux, proximo;
	p = nodo;
	encontrado = false;
	p1 = &nodo;
	while ((i < clave.length()) && (p != NULL)) {
		proxAux = clave[i];
		/*	Si de este nodo que estoy considerando se desprenden más ramas que aquélla en la que se encontraría el elemento a borrar o bien 
			termina un elemento que se encuentra en el conjunto y no llegué al final del String, guardo el nodo en p1, ya que a partir de aquí
			tendré que borrar los nodos, de ser una rama de ahora en más hasta el ultimo caracter del String.
		*/
		i++;
		if ( (p -> finClave | hayMasRamas(*p, char2nat(proxAux))) ) {
			p1 = &(p -> hijos[char2nat(proxAux)]);
			proximo = proxAux;
		}
		p = p -> hijos[char2nat(proxAux)];	
	}
	if (p != NULL) 	{
		if ((p -> finClave) && i <= clave.length()) 
			encontrado = true;
	}
	// si encontramos el elemento lo eliminamos de la lista y del trie
	if (encontrado)	{
		// eliminamos el elemento de la lista
		cClaves.eliminar(clave);		
		// eliminamos el elemento del trie
		if (esUnaHoja (*p)) {
			borrarRama(p1);
		}else {
			(p -> finClave) = false;	
			
		}
	}	

}

template<class T>
ostream & operator << (ostream &o, const DiccTrie< T > &esp) {
	IteradorConjString it(esp.cClaves);
	string st;
	while (it.tieneProximo()) {
		st=it.proximo();
		o << st << "=> ( " << esp.obtener(st) << " )" << endl;
	}
	return o;
}

template <class T>
DiccTrie<T> & DiccTrie<T>::operator=(const DiccTrie<T> &otro) {
	if (this != &otro) {
		//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!FALTA BORRAR cCaves
		string clave;
		delete nodo;
		IteradorConjString aux (otro.cClaves);
		while (aux.tieneProximo()) {
			clave = aux.proximo();
			this -> definir(clave, otro.obtener(clave));
		}
						
	}
	return *this;
}
#endif
